package com.ssh;

import org.junit.Test;

public class FindCircleNum_547 {
	private int n;
	public int findCircleNum(int[][] M) {
		n = M.length;
		int sum = 0;
		boolean[] hasVisited = new boolean[n];
		for (int i = 0; i < n; i++) {
			if (!hasVisited[i]) {
				dfs(M, i, hasVisited);
				sum++;
			}
		}
		return sum;
    }
	private void dfs(int[][] M, int i, boolean[] hasVisited) {
		hasVisited[i] = true;
		for (int j = 0; j < n; j++) {
			if (M[i][j] == 1 && !hasVisited[j]) {
				dfs(M, j, hasVisited);
			}
		}
	}
	
	@Test
	public void test() {
		int[][] a = /*{{1,1,0},
					 {1,1,0},
					 {0,0,1}};*/
			  {  {1,1,0,0},
				 {1,1,0,0},
				 {0,1,1,0},
				 {0,0,0,1}
				 };
		System.out.println(findCircleNum(a));
	}
	
}
